package com.lw.leetcode.arr.b;

import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

/**
 * 274. H 指数
 * 275. H 指数 II
 *
 * @Author liw
 * @Date 2021/5/7 10:58
 * @Version 1.0
 */
public class HIndex {

    public static void main(String[] args) {
        HIndex test = new HIndex();
//        int[] arr = {3,10};
        int[] arr = {0};
//        int[] arr = {100};
//        int[] arr = {3,0,6,1,5};
//        int[] arr = {1,3,1};
//        int[] arr = {1,2,100};
        int i = test.hIndex3(arr);
        int r = test.hIndex(arr);
        System.out.println(i);
        System.out.println(r);
    }

    public int hIndex2(int[] citations) {
        Map<Integer, Integer> map = new TreeMap<>((a, b) -> b - a);
        for (int num : citations) {
            map.merge(num, 1, (a, b) -> a + b);
        }
        int sum = 0;
        a:
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer key = entry.getKey();
            Integer value = entry.getValue();
            for (Integer i = 0; i < value; i++) {
                sum++;
                if (sum > key) {
                    sum--;
                    break a;
                }
                if (sum == key) {
                    break a;
                }
            }
        }
        return sum;
    }


    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int length = citations.length;
        int end = length - 1;
        if (citations[end] == 0) {
            return 0;
        }
        int st = 0;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            int t = length - m;
            if (citations[m] >= t) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        return length - st;
    }

    /*
     * 思路：
     *
     * 1、首先看到h个元素大于等于某个值，N-h个元素小于等于某个值，这显然是一个有序序列的特征，所以自然而然的想到先将数组排序；
     *
     * 2、将数组排序之后，对于给定的某个i，我们知道有citations.length - i篇论文的引用数 ≥ citations[i]，i篇
     *    论文的引用数 ≤ citations[i]；
     *
     * 3、不妨设h = citations.length - i，即至多有h篇论文分别引用了至少citation[i]次，其余citations.length - h篇
     *    论文的引用数不多于citation[i]次。
     *
     *    既然如此，只要citation[i] ≥ h，就满足题意。
     */
    public int hIndex3(int[] citations) {
        Arrays.sort(citations);
        int length = citations.length;
        for (int i = 0; i < length; i++) {
            int h = length - i;
            if (h <= citations[i]) {
                return h;
            }
        }
        return 0;
    }

}
